1. For deadlock detection, the system must provide
1. An algorithm that examines the state of the system to detect whether a deadlock has occurred
2. And an algorithm to recover from the deadlock
2. A detection-and-recovery scheme requires various kinds of overhead
1. Run-time costs of maintaining necessary information and executing the detection algorithm
2. Potential losses inherent in recovering from a deadlock

• Requires the creation and maintenance of a wait-for graph
•  Consists of a variant of the resource-allocation graph
• The graph is obtained by removing the resource nodes from a resource-allocation graph and collapsing the appropriate edges
•  Consequently; all nodes are processes
•  Pi ® Pj   if Pi is waiting for Pj.
• Periodically invoke an algorithm that searches for a cycle in the graph
• If there is a cycle, there exists a deadlock
• An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph

• Resource-Allocation Graph and Wait-for Graph
  

Required data structures:

1. Available:  A vector of length m indicates the number of available resources of each type.
2. Allocation:  An n x m matrix defines the number of resources of each type currently allocated to each process.
3. Request:  An n x m matrix indicates the current request  of each process.  If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj.

Detection-Algorithm Usage

1. When, and how often, to invoke the detection algorithm depends on:
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it happens?
2. If the detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which one of the many deadlocked processes “caused” the deadlock
3. If the detection algorithm is invoked for every resource request, such an action will incur a considerable overhead in computation time
4. A less expensive alternative is to invoke the algorithm when CPU utilization drops below 40%, for example
1. This is based on the observation that a deadlock eventually cripples system throughput and causes CPU utilization to drop